import functools


class Solution(object):
    def shortestSuperstring(self, words):
        n = len(words)
        DP = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i != j:
                    m1 = len(words[i])
                    for k in range(m1):
                        if words[i][k:] == words[j][: m1 - k]:
                            DP[i][j] = m1 - k
                            break
        @functools.cache
        def dfs(val, now_node):
            last_val = val ^ (1 << now_node)
            if last_val == 0:
                return len(words[now_node]), [now_node]
            else:
                min_len = float('inf')
                for node in range(n):
                    if (last_val >> node) & 1:
                        last_len, last_list = dfs(last_val, node)
                        now_len = last_len + len(words[now_node]) - DP[node][now_node]
                        if now_len < min_len:
                            min_list = last_list
                            min_len = now_len
                return min_len, min_list + [now_node]

        min_len = float('inf')
        max_val = (1 << n) - 1
        for i in range(n):
            now_val, now_list = dfs(max_val, i)
            if now_val < min_len:
                min_len = now_val
                ans_list = now_list
        ans = [words[ans_list[0]]]
        for i in range(1, n):
            ans.append(words[ans_list[i]][DP[ans_list[i - 1]][ans_list[i]]:])
        return ''.join(ans)


data = Solution()
words = ["catg","ctaagt","gcta","ttca","atgcatc"]
print(data.shortestSuperstring(words))
words = ["alex","loves","leetcode"]
print(data.shortestSuperstring(words))